"""
235. 二叉搜索树的最近公共祖先
树 深度优先搜索 二叉搜索树 二叉树
简单


给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]



 

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
 

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree
"""
from typing import List


class TreeNode:
    def __init__(self, x, left=None, right=None):
        self.val = x
        self.left = left
        self.right = right

    def __str__(self):
        return '{}({},{})'.format(self.val, self.left, self.right)


class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def get_path(r_node: 'TreeNode', t_node: 'TreeNode') -> List['TreeNode']:
            path = []
            cur = r_node
            while cur:
                path.append(cur)
                if cur.val == t_node.val:
                    break
                elif t_node.val < cur.val:
                    cur = cur.left
                else:
                    cur = cur.right
            return path

        p_path = get_path(root, p)
        q_path = get_path(root, q)
        min_len = min(len(p_path), len(q_path))
        res = None
        index = 0
        while p_path and q_path and index < min_len:
            if p_path[index].val != q_path[index].val:
                break
            res = p_path[index]
            index += 1
        return res


if __name__ == '__main__':
    solution = Solution()

    n = TreeNode(6,
                 left=TreeNode(2, left=TreeNode(0), right=TreeNode(4, left=TreeNode(3), right=TreeNode(5))),
                 right=TreeNode(8, left=TreeNode(7), right=TreeNode(9)))
    result = solution.lowestCommonAncestor(n, TreeNode(2), TreeNode(8))
    print(result)
    assert result and result.val == 6

    result = solution.lowestCommonAncestor(n, TreeNode(2), TreeNode(4))
    print(result)
    assert result and result.val == 2
